package com.shm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 851. 喧闹和富有
 * 有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person x "。
 *
 * 给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自恰（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况 ）。
 *
 * 现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
 * 输出：[5,5,2,5,4,5,6,7]
 * 解释：
 * answer[0] = 5，
 * person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。
 * 唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7，
 * 但是目前还不清楚他是否比 person 0 更有钱。
 * answer[7] = 7，
 * 在所有拥有的钱肯定不少于 person 7 的人中（这可能包括 person 3，4，5，6 以及 7），
 * 最安静（有较低安静值 quiet[x]）的人是 person 7。
 * 其他的答案也可以用类似的推理来解释。
 * 示例 2：
 *
 * 输入：richer = [], quiet = [0]
 * 输出：[0]
 *
 * 提示：
 *
 * n == quiet.length
 * 1 <= n <= 500
 * 0 <= quiet[i] < n
 * quiet 的所有值 互不相同
 * 0 <= richer.length <= n * (n - 1) / 2
 * 0 <= ai, bi < n
 * ai != bi
 * richer 中的所有数对 互不相同
 * 对 richer 的观察在逻辑上是一致的
 * @author SHM
 */
public class LoudAndRich {
    /**
     * 方法一：深度优先搜索
     * 我们可以根据 \textit{richer}richer 构建一张有向图：把人看成点，如果 a_ia
     * i
     * ​
     *   比 b_ib
     * i
     * ​
     *   更有钱，那么就从 b_ib
     * i
     * ​
     *   向 a_ia
     * i
     * ​
     *   连一条有向边。由于题目保证 \textit{richer}richer 中所给出的数据逻辑自恰，我们得到的是一张有向无环图。
     *
     * 因此我们从图上任意一点（设为 xx）出发，沿着有向边所能访问到的点，都比 xx 更有钱。
     *
     * 题目需要计算拥有的钱肯定不少于 xx 的人中，最安静的人。我们可以分为拥有的钱肯定与 xx 相等，以及拥有的钱肯定比 xx 多两种情况。对于前者，根据题目所给信息，我们只知道 xx 拥有的钱肯定与自己相等，无法知道是否有其他人拥有的钱肯定与 xx 相等；对于后者，我们可以先计算出 xx 的邻居的 \textit{answer}answer 值，再取这些 \textit{answer}answer 值中的最小值为结果，这是因为从 xx 的邻居出发所能访问到的点，并上 xx 的邻居后所得到的点集，就是从 xx 出发所能访问到的点。总的来说，最安静的人要么是 xx 自己，要么是 xx 的邻居的 \textit{answer}answer 中最安静的人。
     *
     * 计算 xx 的每个邻居的 \textit{answer}answer 值是一个递归的过程，我们可以用深度优先搜索来实现。为避免重复运算，在已经计算出 \textit{answer}[x]answer[x] 的情况下可以直接返回。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n+m)O(n+m)，其中 nn 是数组 \textit{quiet}quiet 的长度，mm 是数组 \textit{richer}richer 的长度。建图和 DFS 的时间复杂度均为 O(n+m)O(n+m)。
     *
     * 空间复杂度：O(n+m)O(n+m)。我们需要 O(n+m)O(n+m) 的空间来记录图中所有的点和边。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/loud-and-rich/solution/xuan-nao-he-fu-you-by-leetcode-solution-jnzm/
     * @param richer
     * @param quiet
     * @return
     */
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int[] ints : richer) {
            g[ints[1]].add(ints[0]);
        }

        int[] ans = new int[n];
        Arrays.fill(ans,-1);
        for (int i = 0; i < n; i++) {
            dfs(i,quiet,g,ans);
        }
        return ans;
    }

    void dfs(int x,int[] quiet,List<Integer>[] g,int[] ans){
        if (ans[x]!=-1){
            return;
        }
        ans[x] = x;
        for (Integer integer : g[x]) {
            dfs(integer,quiet,g,ans);
            if (quiet[ans[integer]]<quiet[ans[x]]){
                ans[x] = ans[integer];
            }
        }
    }
}
